Many communications systems currently use encryption to enhance security of the systems. These communication systems include but are not limited to cellular radio telephone communication system, personal communication systems, paging systems, as well as wireline and wireless data networks. By way of example a cellular communication system will be described below; however, it will be appreciated by those skilled in the art that the encryption techniques described can be readily extended to other communication systems without departing from the scope and spirit of the present invention.
Turning now to cellular communication systems, these systems typically include subscriber units (such as mobile or portable units) which communicate with a fixed network communication unit via radio frequency (RF) communication links. In cellular communication systems, the RF communication link is the primary target for cryptographic systems, because it is the most vulnerable to unauthorized introduction (spoofing) or extraction (eavesdropping) of information. It is well known in the art that information in these communication links may be cryptographically protected by encrypting them with a pseudo-noise (PN) signal which is pseudo-random in nature. For example this may be accomplished by performing an exclusive-or operation of an information signal with a PN signal, prior to transmission. Subsequently, the inverse operation can be performed during the receiving process.
The PN signals are not truly random, but appear random when subject to cursory inspection. The advantage of these PN signals is that they can be easily generated by a linear feedback shift register (LFSR). An LFSR generates a PN signal which is periodic (i.e., deterministic). The periodicity of the PN signal is dependent on the number of stages (i.e., bits stored) in the register, the feedback "taps", and the initial state of the LFSR stages. The LFSR implements an Nth degree polynomial (where N is the number of stages of the LFSR) by having one feedback signal "tap" (output bit of a stage) for each coefficient of the polynomial. An input bit is formed from an exclusive-or operation on the outputs of these feedback signal "taps" and feed back into the register. Ideally feedback "taps" can be chosen which implement a maximal length PN signal generator. A maximal length PN generator generates a pseudo random sequence which repeats every 2.sup.N -1 cycles, where N is the number of stages in the in the register. Examples of maximal length feedback tap arrangements for several different stage length registers are given in "Error-Correcting Codes", second edition by W. Wesley Peterson and E. J. Weldon, Jr., MIT Press, 1972.
The problem with using PN generators to cryptographically protect an information signal is that they are extremely vulnerable to attack (i.e., the encryption is easy to crack or break). The weakness of PN generators which are based on an LFSR is primarily due to the inherent linearity of the generators. Since PN generators operate according to an algorithm, knowledge of the algorithm reveals the entire sequence. Further, as noted in chapter 5 of "Cipher Systems" by Henry Baker and Fred Piper, Northwood Publications, 1992, a cryptoanalyst needs only 2N bits of plaintext and corresponding ciphertext for an N stage long LFSR to be able to determine the feedback "taps", the initial state of the LFSR, and ultimately any PN signal output by the LFSR. This vulnerability represents a major drawback to the continued use of the LFSR to cryptographically protect communication systems.
Therefore, a need exists for a cryptographically protection technique for communication systems which can alleviate these problems.